package lhc.alg.top100;

/**
 * description: https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/
 *  dfs 深度优先遍历 + 备忘录 降低时间复杂度
 *  O(mn) O(mn)
 * author: hongchen.liao
 * date:  2022/8/13
 */
public class _329_Longest_Increasing_Path_in_a_Matrix {


    class Solution {
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        int rows, cols;
        public int longestIncreasingPath(int[][] matrix) {
            if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
                return 0;
            }
            rows = matrix.length;
            cols = matrix[0].length;
            int[][] memo = new int[rows][cols];
            int ans = 0;
            for(int i = 0; i < rows; i++){
                for(int j = 0; j < cols; j++){
                    ans = Math.max(ans, dfs(matrix, i, j, memo));
                }
            }
            return ans;
        }

        int dfs(int[][] matrix, int r, int c, int[][] memo){
            if(memo[r][c] != 0){
                return memo[r][c];
            }
            ++memo[r][c];
            for(int[] dir : dirs){
                int newR = r + dir[0], newC = c + dir[1];
                if(newR >= 0 && newR < rows && newC >= 0 && newC < cols && matrix[newR][newC] > matrix[r][c]){
                    memo[r][c] = Math.max(memo[r][c] , dfs(matrix, newR, newC, memo)+1);
                }
            }
            return memo[r][c];
        }
    }



}
